import java.util.Arrays;

/**
 * @projectName: java-daily-questions
 * @package: PACKAGE_NAME
 * @className: QuickSort
 * @author: ZM
 * @description: 快速排序
 * @date: 2021/8/16 15:16
 * @version: 1.0
 */
public class QuickSort {

    public static int[] sort(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }
        int[] nums = new int[arr.length];
        System.arraycopy(arr, 0, nums, 0, arr.length);
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void sort(int[] arr, int low, int high) {
        if(low < high) {
            // 获取基准值，在整个区间内，大于index在其右边，小于index在其左边
            int index = getIndex(arr, low, high);
            //
            sort(arr, low, index -1);
            sort(arr, index + 1, high);
        }
    }

    private static int getIndex(int[] arr, int low, int high) {
        int temp = arr[low];
        System.out.println("temp = " + temp);
        while(low < high) {
            // 从右向左，队尾的元素小于等于temp，high就向前挪动指针
            while (low < high && arr[high] >= temp) {
                high--;
            }
            // 队尾元素比temp小，赋值为low
            arr[low] = arr[high];
            System.out.println("移动：" + Arrays.toString(arr));
            //（从左往右）当队首元素小于等于temp,向后挪动low指针
            while (low < high &&arr[low] <= temp) {
                low++;
            }
            // 当队首元素大于tmp时,需要将其赋值给high
            arr[high] = arr[low];
            System.out.println("移动：" + Arrays.toString(arr));
        }
        // temp正确位置
        arr[low] = temp;
        System.out.println("移动：" + Arrays.toString(arr));
        return low;
    }

    public static void main(String[] args) {
        int[] arr = {10, 4, 2, 7, 5, 19, 11, 33, 28};

        System.out.println("原数组：" + Arrays.toString(arr));
        System.out.println("排序后：" + Arrays.toString(sort(arr)));
    }
}
